package algorithms.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 1.荷兰国旗问题引出快排1.0，2.0;时间复杂度O(n^2)
 * 2.加入随机特性实现快排3.0;时间复杂度O(N*logN)
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = GetRandomArr.getRandomArr(10);
        //dutchFlag01(arr, 5);
        //dutchFlag02(arr,5);
//        quickSort01(arr,0,arr.length-1);
        //quickSort02(arr,0,arr.length-1);
        quickSort03(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        System.out.println(arr.length);
    }

    /**
     * 交换
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr,int i,int j) {
        if(i == j)
            return;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    /**
     * 荷兰国旗：
     * 问题一
     * 给定一个数组arr,和一个数num,请把小于等于num的数放在数组的左边，大于num的
     * 数放在数组的右边。要求额外空间复杂度0(1)，时间复杂度0(n)
     *
     * 思路：
     *     1.[i] <= num:和<=区域的下一个数交换，<=区扩大，i++;
     *     2.[i] > num:i++;
     *  数据越界结束
     *
     */
    public static void dutchFlag01(int[] arr,int num) {
        int lessThan = -1;//  小于区的边界
        for(int i = 0;i < arr.length && lessThan < arr.length-1;i++) {
            // [i] <= num,和<=区域的下一个数交换，<=区扩大，i++;
            if(arr[i] <= num) {
                swap(arr,i,lessThan+1);
                lessThan++;
            }
            // [i] > num:i++;
        }
        System.out.println(num+" 的 <= 区的边界:"+lessThan+" 数值："+Arrays.toString(Arrays.copyOfRange(arr,0,lessThan+1)));
    }

    /**
     * 问题二（荷兰国旗问题）
     * 给定一个数组arr,和一个数num,请把小于num的数放在数组的左边，等于num的数放
     * 在数组的中间，大于um的数放在数组的右边。要求额外空间复杂度0(1)，时间复杂度0(N)
     *
     * 思路：
     *      1.[i] < num : [i]和<区的下一个交换，<右扩，i++;
     *      2.[i] = num : i++;
     *      3.[i] > num : [i]和>区的前一个交换，>左扩，i不变
     *  i与大于区相撞结束
     */
    public static void dutchFlag02(int[] arr,int num) {
        int lt = -1;//  小于区的边界
        int gt = arr.length;//  大于区的边界
        for(int i = 0;i < gt;) {
            // 1.[i] < num : [i]和<区的下一个交换，<右扩，i++;
            if(arr[i] < num) {
                swap(arr,i,lt + 1);
                lt++;
                i++;
            }
            // 2.[i] = num : i++;
            else if (arr[i] == num)
                i++;
            // 3.[i] > num : [i]和>区的前一个交换，>左扩，i不变
            else {
                swap(arr,i,gt - 1);
                gt--;
            }
        }
        System.out.println(num+" 的 < 区的边界:"+lt+" 数值："+
                Arrays.toString(Arrays.copyOfRange(arr,0,lt+1)));
        System.out.println(num+" 的 > 区的边界:"+gt+" 数值："+
                Arrays.toString(Arrays.copyOfRange(arr,gt,arr.length)));
        System.out.println(num+" 的 = 区的边界:["+lt+","+gt+"] 数值："
                +Arrays.toString(Arrays.copyOfRange(arr,lt+1,gt)));
    }

    /**
     * 快排1.0
     *
     * @param arr
     * @param l
     * @param r
     */
    public static void quickSort01(int[] arr,int l,int r) {
        if(l < r) {
            int index = partition01(arr,l,r);
            quickSort01(arr,l,index-1);// 左边
            quickSort01(arr,index+1,r);// 右边
        }
    }
    public static int partition01(int[] arr,int l,int r) {
        int num = arr[r];
        int lt = l-1;//  小于区的边界
        for(int i = l;i <= r-1 && lt <= r-2;i++) {// i <= r-1:最后一个位置是比较位置，lt <= r-2：”<=“区域与最后一个位置相撞。
            // 1.[i] <= num,和<=区域的下一个数交换，<=区扩大，i++;
            if(arr[i] <= num) {
                swap(arr,i,++lt);
            }
            // 2.[i] > num:i++;
        }
        // 将比较值和小于区域的后一个值交换;
        swap(arr,lt+1,r);
        System.out.println(num+" 的 <= 区的边界:"+lt+" 数值："
                +Arrays.toString(Arrays.copyOfRange(arr,0,lt+1)));
        return lt+1;// 返回查找元素的下标
    }

    /**
     * 快排2.0
     *
     * @param arr
     * @param l
     * @param r
     */
    public static void quickSort02(int[] arr,int l,int r) {
        if( l < r ) {
            int[] range = partition02(arr,l,r);
            quickSort02(arr,l,range[0]-1);// 左边
            quickSort02(arr,range[1]+1,r);// 右边
        }
    }
    public static int[] partition02(int[] arr,int l,int r) {
        int num = arr[r];
        int lt = l-1;//  小于区的边界
        int gt = r;//  大于区的边界
        for(int i = l;i < gt;) {
            // 1.[i] < num : [i]和<区的下一个交换，<右扩，i++;
            if(arr[i] < num) {
                swap(arr,i++,++lt);
            }
            // 2.[i] = num : i++;
            else if (arr[i] == num)
                i++;
                // 3.[i] > num : [i]和>区的前一个交换，>左扩，i不变
            else {
                swap(arr,i,--gt);
            }
        }
        // 将大于区域的数与最后一个比较值交换。
        swap(arr,gt,r);
//        System.out.println(num+" 的 < 区的边界:"+lt+" 数值："+
//                Arrays.toString(Arrays.copyOfRange(arr,0,lt+1)));
//        System.out.println(num+" 的 > 区的边界:"+gt+" 数值："+
//                Arrays.toString(Arrays.copyOfRange(arr,gt,r)));
//        System.out.println(num+" 的 = 区的边界:["+(lt+1)+","+(gt-1)+"] 数值："
//                +Arrays.toString(Arrays.copyOfRange(arr,lt+1,gt)));
//        System.out.println("结果："+Arrays.toString(arr));
        return new int[]{lt+1,gt};// 返回查找元素的下标,第一个为<区，第二个为>区
    }

    /**
     * 快排3.0 （最终版）
     * 加入随机特性实现快排3.0;时间复杂度O(N*logN)
     * @param arr
     * @param l
     * @param r
     */
    public static void quickSort03(int[] arr,int l,int r) {
        if( l < r ) {
            // 随机取一个数值与最后一个交换
            swap(arr,(int)(Math.random()*(r-l+1)),r);
            // 将选择最后一个数将l,r区域弄成: [ < 区域 | = 区域 | > 区域 ]
            int[] range = partition03(arr,l,r);
            quickSort02(arr,l,range[0]-1);// 左边 <
            quickSort02(arr,range[1]+1,r);// 右边 >
        }
    }

    public static int[] partition03(int[] arr,int l,int r) {
        int num = arr[r];
        int lt = l-1;//  小于区的边界
        int gt = r;//  大于区的边界
        for(int i = l;i < gt;) {
            // 1.[i] < num : [i]和<区的下一个交换，<右扩，i++;
            if(arr[i] < num) {
                swap(arr,i++,++lt);
            }
            // 2.[i] = num : i++;
            else if (arr[i] == num)
                i++;
                // 3.[i] > num : [i]和>区的前一个交换，>左扩，i不变（@FIXME i不变是因为交换过来的值是未知的,等下一次进行比较）
            else {
                swap(arr,i,--gt);
            }
        }
        // 将大于区域的数与最后一个比较值交换。
        swap(arr,gt,r);
        return new int[]{lt+1,gt};// 返回查找元素的下标,第一个为=区的左边界，第二个为=区的右边界
    }

}
